Academic Open Internet Journal ISSN 1311-4360 |
Volume 18, 2006 |
TRACEBACKING
V.
Murali Bhaskaran1 A.
M. Natarajan2 S.
N. Sivanandam3
Internet Protocol (IP) packet traceback system is to identify the origin
of sequences of IP packets when the sources IP packet address of these packets
are spoofed. IP packet traceback is usually performed at the network layer,
with the help of routers and gateways. Several approaches have been proposed to
trace IP packets to their origin. The packet marking approach enables routers
to probabilistically mark packets with partial path information and tries to
reconstruct the complete path from the marked packets. In the most of these
approaches, routers and victims (affected systems) are considerably overloaded
for marking the packet and reconstructing trace path
and also more marked packets are required. This paper focuses on tracing the
approximate source of attack with a single packet, with the spoofed source
address, without computation by victim. Also, the method helps to identify and
eliminate the malicious traffic from bad source. In addition, it also provides
more bandwidth for effective traffic from the poor sources to the victim in a
single Internet Service Provider (
Keywords: Victim, Internet Service Provider (ISP), Traceback,
Routers, Spoofing, IP Packets
1.
Introduction
Each Internet packet in the
Internet carries a destination address and a source address. The network routers use the destination
address while forwarding the packets. The source address is only needed by the
final destination to reply. Like the Indian postal return addresses, the source
address is ignored or can be forged or spoofed. Normal network applications
provide legitimate source addresses, but a hacker can persuade an operating
system to use spoofed addresses for the source address. Spoofed addresses can be used to hide one’s
network identity or directly return packets to another host/target. Spoofed
addresses can also be used to masquerade as another host which is possibly
trusted by the target host. Spoofed addresses have been used in the Internet
attacks[1][2], namely Denial of Services (DoS) attack
and Distributed Denial of Services (DDoS) attack,
providing bogus packet flow to hide real source of attack, masquerading,
stealth/idle scanning and so on.
The key requirements for IP
traceback methods include
In
practice, backtracking is complicated for many reasons. It is a slow process;
the flow must stay active during the traceback (like tracing a phone call); the
flow may come from multiple sources and have varying signatures. One or more
routers along the path may not have the facility for identifying the upstream
source and one may need physical access to some routers to enable backtracking.
Router personnel may be unavailable to assist and eventually, one starts to
cross into other administrative domains or countries and encounter
legal/political obstacles.
One promising solution
proposed by Savage etal.[10]
is to let routers probabilistically mark packets with partial path information
during packet forwarding. The victim then reconstructs the complete path after
receiving a modest number of packets that contain the marking. This approach
has a low overhead for routers and the network and supports incremental
deployment.
2.
The Proposed System
Traceback schemes usually rely on router assistance
to determine the path followed by the attack packets and eventually identify
the attack source. All the approaches referred in [10][4][7][8][13]
require a collection of large number of
packets before starting the traceback process. Our aim is to identify the source of the
spoofed packets and also to prevent the attack at the nearest point to the
source in a single ISP domain. This method is similar to [6] where the
network is divided into ISP domains and customers are connected to these ISP
domains. In general, there are two types of routers in an ISP domain: internal
routers and external routers. Internal routers belong to the ISP domain and
external routers belong to the customers or another ISP. Internal routers are
divided into two types, based on location, namely, edge routers and transit
routers. Edge routers are internal routers that are adjacent to one or more
external routers. Transit routers are internal routers that are only adjacent
to other internal routers. (See Figure-1)
Figure-1 Types of Routers based on location
In Figure-2 (R0….R6) are
edge routers and (R7,R8,R9)
are transit routers. While there is a chance for attack on traffic to originate
from the internal routers within the ISP domain (A3 in Figure-1), often most
attacks originate from outside the ISP domain and targets the victim which is
also outside the ISP domain. Our aim is
to prevent the attack at the nearest point to the source of attack in a single
Figure-2 Single ISP Backbone
network.
(
R0..R9- Routers, A1..A4-Attacks,V- Victim )
Our
system involves a Controller and Agent model. In each
2.1.
Packet Marking
In recent years several
packet-marking techniques have been proposed. Since packets are
probabilistically marked, the victim would need large number of packets to
calculate the total path traversed by the attack on traffic. Even if it is
assumed that each packet is marked, it could take a considerable amount of time
for the victim to calculate the path, a computation needs to retrieve the
32-bit IP address of the marked router. In general, the time taken to
reconstruct the path is dependent on the number of attacking systems, number of
parallel paths and length of the path.
Figure -3 Marking in the identification field of the
IP packet header
Any system on the Internet is identified by using a
32-bit IP address. An efficient packet marking technique can be developed by an
8- bit or 16-bit coding instead of 32-bit IP address to identify the system on
the Internet. Our approach is based on
the Controller-Agent model and is implemented within the ISP; there is no need
to identify each router with its 32-bit IP address as long as the controller
can uniquely identify each agent with a different identifier. Each agent in the
domain is assigned a 10-bit agent ID against its 32-bit IP address and a 6-bit
controller ID is used. So that, a maximum of 1024 (210
) agent IDs only can be assigned
in a single
2.2. Controller Mechanism
The controller can be implemented on a dedicated host
or on any one of the transit routers in a domain. It responds to the victim’s
request and sends commands to its agents. However in our case, there is no need
for the controller to identify the attack. Hence the implementation of the
controller is much simpler. The controller can identify its agents using the
unique agents’ IDs and all the agents can identify its controller with the
controller ID.
There
are two important commands, from the controller to its agents.
1. The first command is issued to all the agents in the
2. The second command is issued when the victim
identifies the attack signature based on the agent ID and requests the
controller to prevent the attack at the identified agent. The controller
retrieves the 32-bit IP address of the agent based on the 10-bit agent ID and
commands the particular agent to prevent the traffic that is matching the
attack signature.
2.3.
Agent Mechanism
The agents are implemented on all edge routers in a
There
are two important stages in the implementation of agent mechanism as shown in
algorithm-1.
Ø
The first stage
is invoked when the agent receives a command from its controller to mark the
traffic to the victim. The command from the controller gives the information of
the victim address, and controller ID. Now the agent dynamically applies a
filter with the destination address of the victim and marks the packet with the
controller ID and agent ID in the identification field. Packets are marked only
by the agent or by the first agent that sees the traffic to the victim. Packets
marked by the attacker are identified and eliminated at this stage.
Ø
The second stage
is invoked when the agent receives a command from its controller to prevent the
attack traffic to the victim. In this stage, the agent drops all the packets
that match the attack signature. All the packets that do not match the attack
signature are again marked with the controller ID and the agent ID and are
destined to the victim. The main reason for marking the packets even if it does
not match the attack signature is to enable the victim to identify if there are
any changes in the traffic pattern for itself and generate a quick response.
Algorithm -1:
Mark_Packet(victim ID)
Step
: 1 Select the packet which
destination address is same as victim ID
Step
: 2 Check if packet already
marked then drop.
Step
: 3. else mark packet
with controller ID and agent ID.
Block_Attack_Traffic(victim ID, Source ID)
1. filter
the if packet matches with Attack Signature then drop
2. else
MarkPacket(victim address).
3.
System Operation
Controller has to maintain a database about all agent IDs (Table-1).
Since agents are deployed on all the edge routers, all the traffic to the
victim are marked with the controller ID and agent ID in the identification
field of the packet. Since the victim knows the controller ID and agent IDs, it
can easily identify different attack signatures.
Table-1: Database
about Agent details
Agent ID ( 10-bits) |
Edge router IP address |
0000000001 |
127.16.1.1 |
0000000010 |
127.16.1.2 |
. |
. |
. |
. |
1111111111 |
127.16.10.100 |
The victim sends request for marking the packets which are reaching to
it. Then controller sends command to all its agents to mark the packets which
have victim address as a destination address. All agents will mark its 6-bit
controller ID and its ID (10 bits) in the identification field of the packet.
Once the victim identifies the attack signature based on the controller ID and
agent ID, it sends request message to the controller to prevent attack traffic.
After receiving the request from the victim, the controller retrieves the
32-bit IP address of the agent from its database, based on the agent ID’s and
sends command to the agent to prevent the attack traffic. The agent who
receives this command will start preventing the traffic that matches the attack
signature from reaching the victim. Only the traffic that is matching with the
attack signature will be dropped at the agent. As the packets are dropped at
the edge router, the traffic congestion gets reduced in the domain thereby
increasing traffic speed. The traffic that does not match the attack signature
will be marked with the controller ID and agent ID. This is to enable the victim to easily track
the changes in attack traffic.
Prevention will be done until the agent receives a reset signal from its
controller. However the packets will be marked for an excess amount of time.
This is very useful for intermittent type of attacks, where attacking systems
do not flood the victim continuously, but send attack traffic at regular
intervals.
The system operates in two ways, Random Packet
marking and On-demand Packet marking. In random packet marking, all the agents
mark the controller ID and agent ID to all packets in the regular interval. In this method
all edge routers are considerably overloaded by packet marking function. In on-demand packet marking method, all the
agents mark controller ID and agent ID in the identification field of packets
which traffic to victim. When there is no attack, the functions of controller
and agents are identical. Approximate
source can be traced with a single packet and since all the packets are marked
at ingress agent, once attack signatures are identified, prevention of attack
traffic is directly near to the attacking source (ingress agent) instead of hop
by hop. Each agent needs to check and prevent only the attack signature passing
through it.
Only one packet is enough to identify the approximate
source of the packet because it is not to trace the path of the packet. Assume
a simple
A1->R6àR8àR0àV A2-> R4àR7àR8àR0àV
A3-> R3àR9àR0àV A4-> R1àR0à V
P1-> R5àR7àR8àR0àV P2-> R2àR9àR0àV
The controller is implemented on transit router R9
and agents are implemented on all the edge routers R0, R1, R2, R3, R4, and R5.
Even if source addresses are spoofed, all the attack traffic from A(1) will have agent ID of R6 (which is R6’s unique agent
ID) in the identification field. So the victim can easily identify different
attack signatures for different attacking systems based on the agent ID (A1 for
R6, A2 for R4, A3 for R3 and A4 for R1) and request the controller to prevent
the attack at the identified agent.
Since the victim identifies that P1 and P2 are good traffic, the agents
at R5 and R2 will not receive any command to prevent traffic. Hence, the poor
traffic is completely protected.
4. Simulation
We have carried out the
simulation experiments to evaluate the proposed scheme using NS-2 simulator [15].
The snapshot of the simulator is given in the Figure-4. Let us assume that, the
controller is implemented in node-1 and agents are implemented in the edge
router node-5 to node-12).
Figure-4 :
Snapshot of the simulator.
Box – Transit router (0-4), Hexagon –
Edge router(5- 12) and
Circle-Customer node(13-18
Source nodes and 19,20 Victims)
The node-18 sends packets to
the node-19 with spoofed source address as node-17. Node-19(victim) will send
reply to node-17 based on the source address in the packets because victim does
not know the original source. This is one type of attack. In this case we have
to find the origin of the packets. Here routers 10,3,0,2 and 8 are involved to
transfer the packets from node-18 to the destination node-19. In PPM method, to
trace the path of the packets, the victim has to know the addresses of all the
routers where the packets have passed through so that, the routers have to mark
its identification information in the packet. More number of marked packets is
required to reconstruct the path. In our system, only edge router-10 will mark
its agent ID into the packet and send it to the destination. All other routers
will do its normal function. After identifying the attack signature, the victim
sends request to the controller to identify the edge router-10 and block the
forthcoming packets. The controller identifies the IP address of edge router-10
from its database and sends command to edge router-10 to block the packets
which has the attack signature.
5.
Analysis
The proposed system introduces packet marking and
packet dropping. In this section, the proposed system is compared (Table-2)
with Probabilistic Packet Marking (PPM-originally
introduced in [10], this scheme was improved in several different ways[8][9][12]), ICMP traceback[5][11] (which takes a
different approach in determining the full path of the attack), Overlay
Network[6] and Hash-based IP traceback system [14].
Table 2-
Comparison of traceback systems
This
proposed scheme possesses the following merits.
·
It is easy to
implement,
·
·
Packet
marking by only one router,
·
No computation
in the victim side to trace the packets ,
·
It is suitable
for a variety of attacks (DoS and DDoS)
,
·
It has low
processing and no bandwidth overhead and
·
It is scalable
(i.e. the amount of additional configuration on other devices needed to add a
single device to the scheme)
The
limitation of the proposed system is to traceback and eliminates the spoofed
packets with in a
6.
Conclusion
The scheme proposed in this paper is relatively
simple and is suitable for incremental deployment. The Controller-Agent design
does not require extra intelligence to identify the attack signatures. This
scheme is not limited by the number of attackers, but by the number of agents
and the infrastructure of the
References
[1].
Computer
Emergency Response Team, “CERT
Advisory CA-98.01: Smurf IP Denial-of-Service Attack via pings,” http://www.cert.org/advisories/CA-98.01.smurf.html
[2].
Computer
Emergency Response Team, “CERT Advisory CA-92.21: TCP SYN Flooding and IP Spoofing Attacks,” http://www.cert.org/advisories/CA-96.21.ping.html
[3].
P. Ferguson and D.Seneie: Network Ingress Filtering Defeating Denial
of Service Attacks which employ IP source Address spoofing, RFC 2267, January
1998
[4].
H. Burch and B. Cheswick, “Tracing Anonymous Packets to Their Approximate
Source,” Proc. USENIX LISA, 2000, pp. 319–327.
[5].
S. M. Bellovin, “ICMP Traceback
Messages,” IETF draft, 2000; http://www.research.att.com/smb/papers/draftbellovin-itrace-00.txt
[6].
R. Stone, “Centertrack: An IP Overlay Network
for Tracking DoS Floods,” Proc. 9th USENIX Sec. Symp., 2000, pp.
199–212.
[7].
Drew Dean, Matt
Franklin and Adam Stubbledield, “An Algebraic
Approach to IP traceback”, In proceedings of NDSS’01, February 2001,
[8].
D. X. Song and
A. Perrig, “Advanced and Authenticated Marking
Schemes for IP Traceback,” Proc. INFOCOM, 2001, vol. 2, pp. 878–886.
[9].
[10]. S. Savage, David Wetherall,
Anna Karlin and Tom Anderson, “Practical Network
Support for IP traceback,”
IEEE/ACM Transaction, Network, Vol.9 no. 3 June 2001, PP. 226-237.
[11]. Allison Mankin, Dan Massey,Chie Lung Wu, S. Felix Wu, Lixia
Zhang, “On Design and Evaluation of "Intention-Driven ICMP Traceback,”
10th International Conference on Computer Communications and Networks (IC3N'2001),
[12]. Micah Adler, "Tradeoffs in Probabilistic Packet
Marking for IP Traceback," In Proceedings of the Theory of Computing, 2002
[13]. John Ioannidis, Steven M. Bellovin,
"Implementing Pushback: Router-Based Defense Against DDoS
Attacks", In Network and Distributed System Security Symposium, NDSS '02,
February 2002
[14]. A. C. Snoeren et al.,
“Single-Packet IP Traceback,” IEEE/ACM Trans. Net., vol. 10, no. 6, Dec.
2002, pp. 721–734.
[15]. NS-2 simulator: www.isi.edu/nsnam/ns/
Technical College - Bourgas,
All rights reserved,
© March, 2000